
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>数据结构模板 · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="../算法/leetCode周赛题解.html" />
    
    
    <link rel="prev" href="7.树论例题.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="1.图论.html">
            
                <a href="1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="2.图论例题.html">
            
                <a href="2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="3.散列表.html">
            
                <a href="3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.4" data-path="4.排序算法.html">
            
                <a href="4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="5.排序列题.html">
            
                <a href="5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.6" data-path="6.树论.html">
            
                <a href="6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.7" data-path="7.树论例题.html">
            
                <a href="7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="3.8" data-path="9.模板.html">
            
                <a href="9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="../算法/leetCode周赛题解.html">
            
                <a href="../算法/leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="../算法/1.时间复杂度.html">
            
                <a href="../算法/1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="../算法/2.深度优先搜索.html">
            
                <a href="../算法/2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="../算法/2.深度优先搜索题目集.html">
            
                <a href="../算法/2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.5" data-path="../算法/3.广度优先搜索.html">
            
                <a href="../算法/3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >数据结构模板</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><li><span class="title-icon "></span><a href="#0-&#x5E38;&#x7528;stl-api"><b></b>0 &#x5E38;&#x7528;STL API</a></li><ul><li><span class="title-icon "></span><a href="#1vector"><b></b>1.vector</a></li><li><span class="title-icon "></span><a href="#2map--set"><b></b>2.map &amp; set</a></li><li><span class="title-icon "></span><a href="#3queue--stack"><b></b>3.queue &amp; stack</a></li><li><span class="title-icon "></span><a href="#4priorityqueue"><b></b>4.priority_queue</a></li><li><span class="title-icon "></span><a href="#5stl&#x6392;&#x5E8F;"><b></b>5.stl&#x6392;&#x5E8F;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;"><b></b>&#x4E00; &#x6811;&#x8BBA;&#x6A21;&#x677F;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x641C;&#x7D22;&#x6811;"><b></b>1.&#x641C;&#x7D22;&#x6811;</a></li><li><span class="title-icon "></span><a href="#2&#x5B57;&#x5178;&#x6811;"><b></b>2.&#x5B57;&#x5178;&#x6811;</a></li><li><span class="title-icon "></span><a href="#3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><b></b>3.AVL&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;</a></li><li><span class="title-icon "></span><a href="#4&#x7EBF;&#x6BB5;&#x6811;"><b></b>4.&#x7EBF;&#x6BB5;&#x6811;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;"><b></b>&#x4E8C; &#x56FE;&#x8BBA;&#x6A21;&#x677F;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x6700;&#x77ED;&#x8DEF;"><b></b>1.&#x6700;&#x77ED;&#x8DEF;</a></li><li><span class="title-icon "></span><a href="#2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><b></b>2.&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;</a></li><li><span class="title-icon "></span><a href="#3&#x5E76;&#x67E5;&#x96C6;"><b></b>3.&#x5E76;&#x67E5;&#x96C6;</a></li><li><span class="title-icon "></span><a href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><b></b>4.&#x62D3;&#x6251;&#x6392;&#x5E8F;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;"><b></b>&#x4E09; &#x6392;&#x5E8F;&#x6A21;&#x677F;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5FEB;&#x6392;&#x6392;&#x5E8F;"><b></b>1.&#x5FEB;&#x6392;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><b></b>2.&#x5F52;&#x5E76;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><b></b>3.&#x9009;&#x62E9;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#4&#x5806;&#x6392;&#x5E8F;"><b></b>4.&#x5806;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><b></b>5.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#6&#x57FA;&#x6570;&#x6392;&#x5E8F;"><b></b>6.&#x57FA;&#x6570;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#7&#x6876;&#x6392;&#x5E8F;"><b></b>7.&#x6876;&#x6392;&#x5E8F;</a></li></ul><li><span class="title-icon "></span><a href="#&#x56DB;-&#x6563;&#x5217;&#x8868;"><b></b>&#x56DB; &#x6563;&#x5217;&#x8868;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;"><b></b>1.&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h2 id="0-&#x5E38;&#x7528;stl-api"><a name="0-&#x5E38;&#x7528;stl-api" class="anchor-navigation-ex-anchor" href="#0-&#x5E38;&#x7528;stl-api"><i class="fa fa-link" aria-hidden="true"></i></a><a name="0-&#x5E38;&#x7528;stl-api" class="plugin-anchor" href="#0-&#x5E38;&#x7528;stl-api"><i class="fa fa-link" aria-hidden="true"></i></a>0 &#x5E38;&#x7528;STL API</h2>
<h3 id="1vector"><a name="1vector" class="anchor-navigation-ex-anchor" href="#1vector"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1vector" class="plugin-anchor" href="#1vector"><i class="fa fa-link" aria-hidden="true"></i></a>1.vector</h3>
<pre><code>push_back()
size()
clear()
at()
front()
back()
pop_back()
</code></pre><h3 id="2map--set"><a name="2map--set" class="anchor-navigation-ex-anchor" href="#2map--set"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2map--set" class="plugin-anchor" href="#2map--set"><i class="fa fa-link" aria-hidden="true"></i></a>2.map &amp; set</h3>
<pre><code>map:
empty()
find()!=ma.end()

set:
insert()
</code></pre><h3 id="3queue--stack"><a name="3queue--stack" class="anchor-navigation-ex-anchor" href="#3queue--stack"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3queue--stack" class="plugin-anchor" href="#3queue--stack"><i class="fa fa-link" aria-hidden="true"></i></a>3.queue &amp; stack</h3>
<pre><code>queue:

push()
front()
pop()


stack():

push()
top()
pop()
</code></pre><h3 id="4priorityqueue"><a name="4priorityqueue" class="anchor-navigation-ex-anchor" href="#4priorityqueue"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4priorityqueue" class="plugin-anchor" href="#4priorityqueue"><i class="fa fa-link" aria-hidden="true"></i></a>4.priority_queue</h3>
<pre><code>qu.top();
qu.pop();
</code></pre><h3 id="5stl&#x6392;&#x5E8F;"><a name="5stl&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#5stl&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5stl&#x6392;&#x5E8F;" class="plugin-anchor" href="#5stl&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>5.stl&#x6392;&#x5E8F;</h3>
<p>lamda:</p>
<pre><code>    vector&lt;node&gt; qu;
    qu.push_back(node(5,3));
    qu.push_back(node(4,6));
    sort(qu.begin(),qu.end(),[](node &amp;x,node &amp;y){ return x.i&lt;y.i;});
    for(auto k:qu){
        cout&lt;&lt;k.i&lt;&lt;&quot; &quot;&lt;&lt;k.j&lt;&lt;endl;
    }
</code></pre><h2 id="&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;"><a name="&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;" class="anchor-navigation-ex-anchor" href="#&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;" class="plugin-anchor" href="#&#x4E00;-&#x6811;&#x8BBA;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00; &#x6811;&#x8BBA;&#x6A21;&#x677F;</h2>
<h3 id="1&#x641C;&#x7D22;&#x6811;"><a name="1&#x641C;&#x7D22;&#x6811;" class="anchor-navigation-ex-anchor" href="#1&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x641C;&#x7D22;&#x6811;" class="plugin-anchor" href="#1&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x641C;&#x7D22;&#x6811;</h3>
<pre><code class="lang-c++"><span class="hljs-keyword">typedef</span> <span class="hljs-keyword">int</span> ElementType;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> TreeNode *BinTree;
<span class="hljs-keyword">struct</span> TreeNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

<span class="hljs-comment">// &#x67E5;&#x627E;&#x9012;&#x5F52;&#x5B9E;&#x73B0; </span>
<span class="hljs-function">BinTree <span class="hljs-title">Find</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST)  <span class="hljs-comment">// &#x5982;&#x679C;&#x6839;&#x7ED3;&#x70B9;&#x4E3A;&#x7A7A;&#xFF0C;&#x8FD4;&#x56DE; NULL </span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>; 
    <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data) <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5C0F;&#xFF0C;&#x53BB;&#x5DE6;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> Find(X,BST-&gt;Left); 
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5927;&#xFF0C;&#x53BB;&#x53F3;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> Find(X,BST-&gt;Right);
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data == X) <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
        <span class="hljs-keyword">return</span> BST;
}

<span class="hljs-comment">// &#x67E5;&#x627E;&#x975E;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">IterFind</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">while</span>(BST){
        <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)
            BST = BST-&gt;Left;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5927;&#xFF0C;&#x53BB;&#x53F3;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
            BST = BST-&gt;Right;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data == X) <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
            <span class="hljs-keyword">return</span> BST;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;
} 

<span class="hljs-comment">// &#x67E5;&#x627E;&#x6700;&#x5C0F;&#x503C;&#x7684;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">FindMin</span><span class="hljs-params">(BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST)    <span class="hljs-comment">// &#x5982;&#x679C;&#x4E3A;&#x7A7A;&#x4E86;&#xFF0C;&#x8FD4;&#x56DE; NULL </span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;  
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Left)   <span class="hljs-comment">// &#x8FD8;&#x5B58;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x6CBF;&#x5DE6;&#x5206;&#x652F;&#x7EE7;&#x7EED;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> FindMin(BST-&gt;Left);
    <span class="hljs-keyword">else</span>  <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
        <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x67E5;&#x627E;&#x6700;&#x5927;&#x503C;&#x7684;&#x975E;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">FindMax</span><span class="hljs-params">(BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(BST)  <span class="hljs-comment">// &#x5982;&#x679C;&#x4E0D;&#x7A7A; </span>
        <span class="hljs-keyword">while</span>(BST-&gt;Right)   <span class="hljs-comment">// &#x53EA;&#x8981;&#x53F3;&#x5B50;&#x6811;&#x8FD8;&#x5B58;&#x5728; </span>
            BST = BST-&gt;Right;
    <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x63D2;&#x5165;</span>
<span class="hljs-function">BinTree <span class="hljs-title">Insert</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST){  <span class="hljs-comment">// &#x5982;&#x679C;&#x4E3A;&#x7A7A;&#xFF0C;&#x521D;&#x59CB;&#x5316;&#x8BE5;&#x7ED3;&#x70B9; </span>
        BST = (BinTree)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> TreeNode));
        BST-&gt;Data = X;
        BST-&gt;Left = <span class="hljs-literal">NULL</span>;
        BST-&gt;Right = <span class="hljs-literal">NULL</span>;
    }<span class="hljs-keyword">else</span>{ <span class="hljs-comment">// &#x4E0D;&#x4E3A;&#x7A7A; </span>
        <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)  <span class="hljs-comment">// &#x5982;&#x679C;&#x5C0F;&#xFF0C;&#x6302;&#x5728;&#x5DE6;&#x8FB9; </span>
            BST-&gt;Left = Insert(X,BST-&gt;Left);
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x5982;&#x679C;&#x5927;&#xFF0C;&#x6302;&#x5728;&#x53F3;&#x8FB9; </span>
            BST-&gt;Right = Insert(X,BST-&gt;Right);
        <span class="hljs-comment">// &#x5982;&#x679C;&#x76F8;&#x7B49;&#xFF0C;&#x4EC0;&#x4E48;&#x90FD;&#x4E0D;&#x7528;&#x505A; </span>
    }
    <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x5220;&#x9664;</span>
<span class="hljs-function">BinTree <span class="hljs-title">Delete</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    BinTree tmp;
    <span class="hljs-keyword">if</span>(!BST)
        <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x8981;&#x5220;&#x9664;&#x7684;&#x5143;&#x7D20;&#x672A;&#x627E;&#x5230;&quot;</span>;
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)   <span class="hljs-comment">// X &#x6BD4;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x503C;&#x5C0F;&#xFF0C;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#x7EE7;&#x7EED;&#x67E5;&#x627E;&#x5220;&#x9664; </span>
        BST-&gt;Left = Delete(X,BST-&gt;Left);
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)   <span class="hljs-comment">// X &#x6BD4;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x503C;&#x5927;&#xFF0C;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x7EE7;&#x7EED;&#x67E5;&#x627E;&#x5220;&#x9664; </span>
        BST-&gt;Right = Delete(X,BST-&gt;Right);
    <span class="hljs-keyword">else</span>{  <span class="hljs-comment">//  &#x627E;&#x5230;&#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9; </span>
        <span class="hljs-keyword">if</span>(BST-&gt;Left &amp;&amp; BST-&gt;Right){  <span class="hljs-comment">// &#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x6709;&#x4FE9;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
            tmp = FindMin(BST-&gt;Right);   <span class="hljs-comment">// &#x627E;&#x5230;&#x53F3;&#x5B50;&#x6811;&#x4E2D;&#x503C;&#x6700;&#x5C0F;&#x7684;</span>
            BST-&gt;Data = tmp-&gt;Data;     <span class="hljs-comment">// &#x7528;&#x627E;&#x5230;&#x7684;&#x503C;&#x8986;&#x76D6;&#x5F53;&#x524D;&#x7ED3;&#x70B9; </span>
            BST-&gt;Right = Delete(tmp-&gt;Data,BST-&gt;Right);    <span class="hljs-comment">// &#x628A;&#x524D;&#x9762;&#x627E;&#x5230;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x6700;&#x5C0F;&#x503C;&#x7ED3;&#x70B9;&#x5220;&#x9664; </span>
        }<span class="hljs-keyword">else</span>{  <span class="hljs-comment">// &#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x53EA;&#x6709;&#x4E00;&#x4E2A;&#x5B69;&#x5B50;&#x7ED3;&#x70B9;&#x6216;&#x6CA1;&#x6709;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
            tmp = BST;
            <span class="hljs-keyword">if</span>(!BST-&gt;Left &amp;&amp; !BST-&gt;Right)  <span class="hljs-comment">// &#x6CA1;&#x6709;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = <span class="hljs-literal">NULL</span>;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Left &amp;&amp; !BST-&gt;Right)  <span class="hljs-comment">// &#x53EA;&#x6709;&#x5DE6;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = BST-&gt;Left;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(!BST-&gt;Left &amp;&amp; BST-&gt;Right)  <span class="hljs-comment">// &#x53EA;&#x6709;&#x53F3;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = BST-&gt;Right;
            <span class="hljs-built_in">free</span>(tmp);
        }
    }
    <span class="hljs-keyword">return</span> BST;
}
</code></pre>
<h3 id="2&#x5B57;&#x5178;&#x6811;"><a name="2&#x5B57;&#x5178;&#x6811;" class="anchor-navigation-ex-anchor" href="#2&#x5B57;&#x5178;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x5B57;&#x5178;&#x6811;" class="plugin-anchor" href="#2&#x5B57;&#x5178;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x5B57;&#x5178;&#x6811;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> MAX_NODE = <span class="hljs-number">1000000</span> + <span class="hljs-number">10</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> CHARSET = <span class="hljs-number">26</span>;
<span class="hljs-keyword">int</span> trie[MAX_NODE][CHARSET] = {<span class="hljs-number">0</span>};
<span class="hljs-keyword">int</span> color[MAX_NODE] = {<span class="hljs-number">0</span>};
<span class="hljs-comment">//&#x4EE3;&#x8868;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x4E2A;&#x6570;</span>
<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-keyword">char</span> *w)</span></span>{
    <span class="hljs-keyword">int</span> len = <span class="hljs-built_in">strlen</span>(w);
    <span class="hljs-comment">//p&#x4EE3;&#x8868;&#x5F53;&#x524D;&#x5728;&#x54EA;&#x4E2A;&#x8282;&#x70B9;</span>
    <span class="hljs-keyword">int</span> p = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;len; i++){
        <span class="hljs-keyword">int</span> c = w[i] - <span class="hljs-string">&apos;a&apos;</span>;
        <span class="hljs-keyword">if</span>(!trie[p][c]){
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
    }
    color[p] = <span class="hljs-number">1</span>;
}

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-keyword">char</span> *s)</span></span>{
    <span class="hljs-keyword">int</span> len = <span class="hljs-built_in">strlen</span>(s);
    <span class="hljs-keyword">int</span> p = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;len; i++){
        <span class="hljs-keyword">int</span> c = s[i] - <span class="hljs-string">&apos;a&apos;</span>;
        <span class="hljs-keyword">if</span>(!trie[p][c]) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        p = trie[p][c];
    }
    <span class="hljs-keyword">return</span> color[p] == <span class="hljs-number">1</span>;
}

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> t,q;
    <span class="hljs-keyword">char</span> s[<span class="hljs-number">20</span>];
    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%d%d&quot;</span>, &amp;t,&amp;q);
    <span class="hljs-keyword">while</span>(t--){
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%s&quot;</span>, s);
        insert(s);
    }
    <span class="hljs-keyword">while</span>(q--){
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">&quot;%s&quot;</span>, s);
        <span class="hljs-keyword">if</span>(search(s)) <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;YES\n&quot;</span>);
        <span class="hljs-keyword">else</span> <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;NO\n&quot;</span>);
    }
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<h3 id="3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><a name="3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;" class="anchor-navigation-ex-anchor" href="#3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;" class="plugin-anchor" href="#3avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>3.AVL&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;malloc.h&gt;</span></span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> AVLNode *AVLTree;
<span class="hljs-keyword">struct</span> AVLNode{
    <span class="hljs-keyword">int</span> data;     <span class="hljs-comment">// &#x5B58;&#x503C; </span>
    AVLTree left;  <span class="hljs-comment">// &#x5DE6;&#x5B50;&#x6811; </span>
    AVLTree right;  <span class="hljs-comment">// &#x53F3;&#x5B50;&#x6811; </span>
    <span class="hljs-keyword">int</span> height;  <span class="hljs-comment">// &#x6811;&#x9AD8; </span>
};
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-comment">// &#x8FD4;&#x56DE;&#x6700;&#x5927;&#x503C; </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">Max</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b)</span></span>{
    <span class="hljs-keyword">return</span> a&gt;b?a:b;
}

<span class="hljs-comment">// &#x8FD4;&#x56DE;&#x6811;&#x9AD8;&#xFF0C;&#x7A7A;&#x6811;&#x8FD4;&#x56DE; -1 </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getHeight</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-keyword">return</span> A==<span class="hljs-literal">NULL</span>?<span class="hljs-number">-1</span>:A-&gt;height;
}

<span class="hljs-comment">// LL&#x5355;&#x65CB;</span>
<span class="hljs-comment">// &#x628A; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x817E;&#x51FA;&#x6765;&#x6302;&#x7ED9; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x518D;&#x5C06; A &#x6302;&#x5230; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#x53BB; </span>
<span class="hljs-function">AVLTree <span class="hljs-title">LLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x6B64;&#x65F6;&#x6839;&#x8282;&#x70B9;&#x662F; A </span>
    AVLTree B = A-&gt;left;  <span class="hljs-comment">// B &#x4E3A; A &#x7684;&#x5DE6;&#x5B50;&#x6811;  </span>
    A-&gt;left = B-&gt;right;   <span class="hljs-comment">// B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x6302;&#x5728; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A; </span>
    B-&gt;right = A;     <span class="hljs-comment">//  A &#x6302;&#x5728; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A; </span>
    A-&gt;height = Max(getHeight(A-&gt;left),getHeight(A-&gt;right)) + <span class="hljs-number">1</span>;
    B-&gt;height = Max(getHeight(B-&gt;left),A-&gt;height) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86; </span>
}

<span class="hljs-comment">// RR&#x5355;&#x65CB;</span>
<span class="hljs-function">AVLTree <span class="hljs-title">RRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x6B64;&#x65F6;&#x6839;&#x8282;&#x70B9;&#x662F; A </span>
    AVLTree B = A-&gt;right;
    A-&gt;right = B-&gt;left;
    B-&gt;left = A;
    A-&gt;height = Max(getHeight(A-&gt;left),getHeight(A-&gt;right)) + <span class="hljs-number">1</span>;
    B-&gt;height = Max(getHeight(B-&gt;left),A-&gt;height) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86; </span>
}

<span class="hljs-comment">// LR&#x53CC;&#x65CB; </span>
<span class="hljs-function">AVLTree <span class="hljs-title">LRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; RR &#x5355;&#x65CB;</span>
    A-&gt;left = RRRotation(A-&gt;left);
    <span class="hljs-comment">// &#x518D; LL &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> LLRotation(A);
}

<span class="hljs-comment">// RL&#x53CC;&#x65CB;</span>
<span class="hljs-function">AVLTree <span class="hljs-title">RLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; LL &#x5355;&#x65CB;</span>
    A-&gt;right = LLRotation(A-&gt;right);
    <span class="hljs-comment">// &#x518D; RR &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> RRRotation(A); 
}

<span class="hljs-function">AVLTree <span class="hljs-title">Insert</span><span class="hljs-params">(AVLTree T,<span class="hljs-keyword">int</span> x)</span></span>{
    <span class="hljs-keyword">if</span>(!T){  <span class="hljs-comment">// &#x5982;&#x679C;&#x8BE5;&#x7ED3;&#x70B9;&#x4E3A;&#x7A7A;&#xFF0C;&#x521D;&#x59CB;&#x5316;&#x7ED3;&#x70B9; </span>
        T = (AVLTree)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> AVLNode));
        T-&gt;data = x;
        T-&gt;left = <span class="hljs-literal">NULL</span>;
        T-&gt;right = <span class="hljs-literal">NULL</span>;
        T-&gt;height = <span class="hljs-number">0</span>;
    }<span class="hljs-keyword">else</span>{  <span class="hljs-comment">// &#x5426;&#x5219;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C; </span>
        <span class="hljs-keyword">if</span>(x &lt; T-&gt;data){  <span class="hljs-comment">// &#x5DE6;&#x5B50;&#x6811; </span>
            T-&gt;left = Insert(T-&gt;left,x);
            <span class="hljs-keyword">if</span>(getHeight(T-&gt;left)-getHeight(T-&gt;right)==<span class="hljs-number">2</span>){  <span class="hljs-comment">// &#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x53F3;&#x5B50;&#x6811;&#x9AD8;&#x5EA6;&#x5DEE;&#x4E3A; 2 </span>
                <span class="hljs-keyword">if</span>(x &lt; T-&gt;left-&gt;data)  <span class="hljs-comment">// LL &#x5355;&#x65CB; </span>
                    T = LLRotation(T); 
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;left-&gt;data &lt; x)  <span class="hljs-comment">// LR&#x53CC;&#x65CB;</span>
                    T = LRRotation(T); 
            }
        }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;data &lt; x){
            T-&gt;right = Insert(T-&gt;right,x);
            <span class="hljs-keyword">if</span>(getHeight(T-&gt;right)-getHeight(T-&gt;left)==<span class="hljs-number">2</span>){
                <span class="hljs-keyword">if</span>(x &lt; T-&gt;right-&gt;data)  <span class="hljs-comment">// RL &#x53CC;&#x65CB; </span>
                    T = RLRotation(T); 
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;right-&gt;data &lt; x)  <span class="hljs-comment">// RR&#x5355;&#x65CB;</span>
                    T = RRRotation(T); 
            }
        }
    }
    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x6811;&#x9AD8; </span>
    T-&gt;height = Max(getHeight(T-&gt;left),getHeight(T-&gt;right)) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> T;
} 


<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    AVLTree T=<span class="hljs-literal">NULL</span>;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span>&gt;&gt;n;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-keyword">int</span> tmp;
        <span class="hljs-built_in">cin</span>&gt;&gt;tmp;
        T = Insert(T,tmp);
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;T-&gt;data;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<h3 id="4&#x7EBF;&#x6BB5;&#x6811;"><a name="4&#x7EBF;&#x6BB5;&#x6811;" class="anchor-navigation-ex-anchor" href="#4&#x7EBF;&#x6BB5;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x7EBF;&#x6BB5;&#x6811;" class="plugin-anchor" href="#4&#x7EBF;&#x6BB5;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x7EBF;&#x6BB5;&#x6811;</h3>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> NumArray {
<span class="hljs-keyword">public</span>:
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ls k&lt;&lt;1   <span class="hljs-comment">//&#x5DE6;&#x5B50;&#x6811;</span></span>
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rs k&lt;&lt;1|1   <span class="hljs-comment">//&#x53F3;&#x5B50;&#x6811;</span></span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; t;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; lazy;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; nums;
    NumArray(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums) {;
        n=nums.size();
        <span class="hljs-keyword">if</span>(n==<span class="hljs-number">0</span>)<span class="hljs-keyword">return</span>;
        t=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        lazy=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        <span class="hljs-keyword">this</span>-&gt;nums=nums;
        build(<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,n<span class="hljs-number">-1</span>);
    }

    <span class="hljs-comment">//push up   ,push up&#x51FD;&#x6570;&#x662F;&#x5173;&#x952E;,&#x8FD9;&#x91CC;&#x662F;&#x533A;&#x95F4;&#x548C;,&#x5982;&#x679C;&#x662F;&#x533A;&#x95F4;&#x6700;&#x5927;&#x503C;,&#x4FEE;&#x6539;pushUp&#x5373;&#x53EF;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{
        t[k]=t[ls]+t[rs];
    }
    <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x5EFA;&#x6811;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>{    <span class="hljs-comment">//k&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;l&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x533A;&#x95F4;&#x7684;&#x5DE6;&#x7AEF;&#x70B9;&#xFF0C;r&#x5219;&#x4E3A;&#x53F3;&#x7AEF;&#x70B9;</span>
        <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x8D4B;&#x503C;&#x5373;&#x53EF;</span>
            t[k] = nums[l];
        <span class="hljs-keyword">else</span>{
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            build(ls,l,m);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x5DE6;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
            build(rs,m+<span class="hljs-number">1</span>,r);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x53F3;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
            pushUp(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;</span>
        }
    }
    <span class="hljs-comment">//&#x70B9;&#x66F4;&#x65B0;</span>
    <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x66F4;&#x65B0; update_point(p,v,1,n,1);</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update_point</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p, <span class="hljs-keyword">int</span> v, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> k)</span></span>{    <span class="hljs-comment">//p&#x4E3A;&#x4E0B;&#x6807;&#xFF0C;v&#x4E3A;&#x8981;&#x52A0;&#x4E0A;&#x7684;&#x503C;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;</span>
        <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x52A0;&#x4E0A;v&#x5373;&#x53EF;</span>
            t[k] += v;    <span class="hljs-comment">//&#x7EBF;&#x6BB5;&#x6811;&#x6570;&#x7EC4;&#x90FD;&#x5F97;&#x5230;&#x66F4;&#x65B0;</span>
        <span class="hljs-keyword">else</span>{
            <span class="hljs-comment">//&#x5148;&#x5220;&#x9664;&#x6807;&#x8BB0;</span>
            pushdown(k);
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            <span class="hljs-keyword">if</span>(p &lt;= m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
                update_point(p, v, l, m, ls);
            <span class="hljs-keyword">else</span>    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
                update_point(p, v, m + <span class="hljs-number">1</span>, r, rs);
            pushUp(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;&#x7684;&#x503C;</span>
        }
    }
    <span class="hljs-comment">//&#x533A;&#x95F4;&#x66F4;&#x65B0;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{
        <span class="hljs-keyword">if</span>(lazy[k])
        {
            <span class="hljs-keyword">int</span> value=lazy[k];
            t[ls]+=value;
            t[rs]+=value;
            lazy[k]=<span class="hljs-number">0</span>;
            lazy[ls]+=value;
            lazy[rs]+=value;
        }
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update_range</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j,<span class="hljs-keyword">int</span> v,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k)</span>
    </span>{
        <span class="hljs-keyword">if</span>(l&gt;=i&amp;&amp;r&lt;=j)
        {
            t[k]+=v;
            lazy[k]+=v;
        }
        <span class="hljs-keyword">else</span>
        {
            pushdown(k);
            <span class="hljs-keyword">int</span> mid=l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(mid&gt;=i)
            {
               update_range(i,j,v,l,mid,ls);
            }
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(mid&lt;=j)
            {
                update_range(i,j,v,mid+<span class="hljs-number">1</span>,r,rs);
            }
            pushUp(k);
        }
    }
    <span class="hljs-comment">//&#x533A;&#x95F4;&#x67E5;&#x8BE2;</span>
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">range_sum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> L,<span class="hljs-keyword">int</span> R,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k)</span></span>{    <span class="hljs-comment">//[L,R]&#x5373;&#x4E3A;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;</span>
        <span class="hljs-keyword">if</span>(L &lt;= l &amp;&amp; r &lt;= R)    <span class="hljs-comment">//&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x771F;&#x5305;&#x542B;&#x4E8E;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x5185;&#xFF0C;&#x5219;&#x8FD4;&#x56DE;&#x7ED3;&#x70B9;&#x4FE1;&#x606F;&#x4E14;&#x4E0D;&#x9700;&#x8981;&#x5F80;&#x4E0B;&#x9012;&#x5F52;</span>
            <span class="hljs-keyword">return</span> t[k];
        <span class="hljs-keyword">else</span>{
            pushdown(k);
            <span class="hljs-keyword">int</span> res = <span class="hljs-number">0</span>;    <span class="hljs-comment">//&#x8FD4;&#x56DE;&#x503C;&#x53D8;&#x91CF;&#xFF0C;&#x6839;&#x636E;&#x5177;&#x4F53;&#x7EBF;&#x6BB5;&#x6811;&#x67E5;&#x8BE2;&#x7684;&#x4EC0;&#x4E48;&#x800C;&#x81EA;&#x5B9A;&#x4E49;</span>
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            <span class="hljs-keyword">if</span>(L &lt;= m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;</span>
                res += range_sum(L,R,l,m,ls);
            <span class="hljs-keyword">if</span>(R &gt; m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x53F3;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;&#xFF0C;&#x6CE8;&#x610F;&#x8FD9;&#x91CC;&#x4E0D;&#x662F;else if&#xFF0C;&#x56E0;&#x4E3A;&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x53EF;&#x80FD;&#x540C;&#x65F6;&#x548C;&#x5DE6;&#x53F3;&#x533A;&#x95F4;&#x90FD;&#x6709;&#x4EA4;&#x96C6;</span>
                res += range_sum(L,R,m+<span class="hljs-number">1</span>,r,rs);
            <span class="hljs-keyword">return</span> res;    <span class="hljs-comment">//&#x8FD4;&#x56DE;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x5F97;&#x5230;&#x7684;&#x4FE1;&#x606F;</span>
        }
    }
};
</code></pre>
<h2 id="&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;"><a name="&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;" class="plugin-anchor" href="#&#x4E8C;-&#x56FE;&#x8BBA;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C; &#x56FE;&#x8BBA;&#x6A21;&#x677F;</h2>
<h3 id="1&#x6700;&#x77ED;&#x8DEF;"><a name="1&#x6700;&#x77ED;&#x8DEF;" class="anchor-navigation-ex-anchor" href="#1&#x6700;&#x77ED;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x6700;&#x77ED;&#x8DEF;" class="plugin-anchor" href="#1&#x6700;&#x77ED;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x6700;&#x77ED;&#x8DEF;</h3>
<h4 id="1dijkstra"><a name="1dijkstra" class="anchor-navigation-ex-anchor" href="#1dijkstra"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1dijkstra" class="plugin-anchor" href="#1dijkstra"><i class="fa fa-link" aria-hidden="true"></i></a>1.Dijkstra</h4>
<pre><code class="lang-c++">    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dijkstra</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; gh, <span class="hljs-keyword">int</span> N, <span class="hljs-keyword">int</span> K)</span> </span>{
        <span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> INF = <span class="hljs-number">0x3f3f3f3f</span>;
        <span class="hljs-keyword">typedef</span> pair&lt;<span class="hljs-keyword">int</span>, <span class="hljs-keyword">int</span>&gt; PII; <span class="hljs-comment">// first:&#x8DDD;&#x79BB;; second: &#x51E0;&#x53F7;&#x70B9;</span>
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; vis(N + <span class="hljs-number">1</span>, <span class="hljs-literal">false</span>); <span class="hljs-comment">// &#x662F;&#x5426;&#x5DF2;&#x5F97;&#x5230;&#x6700;&#x77ED;&#x8DDD;&#x79BB;</span>
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dist(N+<span class="hljs-number">1</span>, INF); <span class="hljs-comment">// &#x8DDD;&#x79BB;&#x8D77;&#x59CB;&#x70B9;&#x7684;&#x6700;&#x77ED;&#x8DDD;&#x79BB;</span>
        <span class="hljs-built_in">unordered_map</span>&lt;<span class="hljs-keyword">int</span>, <span class="hljs-built_in">vector</span>&lt;PII&gt;&gt; graph; <span class="hljs-comment">// &#x90BB;&#x63A5;&#x8868;&#xFF1B;u-&gt;v,&#x6743;&#x91CD;w</span>
        priority_queue&lt;PII, <span class="hljs-built_in">vector</span>&lt;PII&gt;, greater&lt;PII&gt;&gt; heap; <span class="hljs-comment">// &#x5C0F;&#x9876;&#x5806;&#xFF1B;&#x7EF4;&#x62A4;&#x5230;&#x8D77;&#x59CB;&#x70B9;&#x7684;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#x548C;&#x70B9;</span>

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &amp;t: gh){ <span class="hljs-comment">// &#x521D;&#x59CB;&#x5316;&#x90BB;&#x63A5;&#x8868;</span>
            graph[t[<span class="hljs-number">0</span>]].push_back({t[<span class="hljs-number">2</span>],t[<span class="hljs-number">1</span>]});
        }

        heap.push({<span class="hljs-number">0</span>, K});
        dist[K] = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">while</span>(heap.size()){
            <span class="hljs-keyword">auto</span> t = heap.top();
            heap.pop();
            <span class="hljs-keyword">int</span> ver = t.second, distance = t.first;
            <span class="hljs-keyword">if</span> (vis[ver]) <span class="hljs-keyword">continue</span>; <span class="hljs-comment">// &#x4E4B;&#x524D;&#x66F4;&#x65B0;&#x8FC7;&#xFF0C;&#x662F;&#x5197;&#x4F59;&#x5907;&#x4EFD;</span>
            vis[ver] = <span class="hljs-literal">true</span>;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &amp;p: graph[ver]){
                <span class="hljs-keyword">if</span> (dist[p.second] &gt; distance + p.first){ <span class="hljs-comment">// &#x7528;t&#x53BB;&#x66F4;&#x65B0;&#x5176;&#x4ED6;&#x70B9;&#x5230;&#x8D77;&#x59CB;&#x70B9;&#x7684;&#x6700;&#x77ED;&#x8DDD;&#x79BB;</span>
                    dist[p.second] = distance + p.first;
                    heap.push({dist[p.second], p.second});
                }
            }
        }
        <span class="hljs-keyword">int</span> ans = *max_element(dist.begin()+<span class="hljs-number">1</span>, dist.end());
        <span class="hljs-keyword">return</span> ans == INF ? <span class="hljs-number">-1</span>: ans;
    }
</code></pre>
<h4 id="2floyd"><a name="2floyd" class="anchor-navigation-ex-anchor" href="#2floyd"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2floyd" class="plugin-anchor" href="#2floyd"><i class="fa fa-link" aria-hidden="true"></i></a>2.floyd</h4>
<pre><code class="lang-c++">    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">floyd</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; gh, <span class="hljs-keyword">int</span> N, <span class="hljs-keyword">int</span> K)</span> </span>{
        <span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> INF = <span class="hljs-number">0x3f3f3f3f</span>;
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; dist(N+<span class="hljs-number">1</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(N+<span class="hljs-number">1</span>,INF));
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;=N ; ++i) {
            dist[i][i]=<span class="hljs-number">0</span>;
        }
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:gh){
            dist[k[<span class="hljs-number">0</span>]][k[<span class="hljs-number">1</span>]]=min(dist[k[<span class="hljs-number">0</span>]][k[<span class="hljs-number">1</span>]],k[<span class="hljs-number">2</span>]);
        }
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>; k &lt;=N ; ++k) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;=N ; ++i) {
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>; j &lt;=N ; ++j) {
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> l = <span class="hljs-number">1</span>; l &lt;=N ; ++l) {
            ans=max(ans,dist[K][l]);
        }
        <span class="hljs-keyword">return</span> ans&gt; INF/<span class="hljs-number">2</span>?<span class="hljs-number">-1</span>:ans;
    }
</code></pre>
<h3 id="2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><a name="2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;" class="anchor-navigation-ex-anchor" href="#2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;" class="plugin-anchor" href="#2&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;</h3>
<h4 id="1prim"><a name="1prim" class="anchor-navigation-ex-anchor" href="#1prim"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1prim" class="plugin-anchor" href="#1prim"><i class="fa fa-link" aria-hidden="true"></i></a>1.Prim</h4>
<pre><code class="lang-c++"><span class="hljs-keyword">typedef</span> pair&lt;<span class="hljs-keyword">int</span>,<span class="hljs-keyword">int</span>&gt; ll;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">prim</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; graph, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dist,<span class="hljs-keyword">int</span> n)</span></span>{
    priority_queue&lt;ll,<span class="hljs-built_in">vector</span>&lt;ll&gt;,greater&lt;ll&gt;&gt; q;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; vis(n+<span class="hljs-number">1</span>, <span class="hljs-literal">false</span>);
    dist[<span class="hljs-number">1</span>]=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> sum=<span class="hljs-number">0</span>;
    q.push({dist[<span class="hljs-number">1</span>],<span class="hljs-number">1</span>});
    <span class="hljs-keyword">while</span>( !q.empty() ){
        <span class="hljs-keyword">int</span> index=q.top().second;
        q.pop();
        <span class="hljs-keyword">if</span>(vis[index])<span class="hljs-keyword">continue</span>;
        <span class="hljs-meta">#&#x52A0;&#x4E0A;&#x8FD9;&#x6761;&#x8FB9;</span>
        sum+=dist[index];
        vis[index]= <span class="hljs-literal">true</span>;
        <span class="hljs-meta">#&#x5BF9;&#x5176;&#x90BB;&#x63A5;&#x8FB9;,&#x6536;&#x5F55;</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;=n ; ++i) {
            <span class="hljs-keyword">if</span>(!vis[i] &amp;&amp; graph[index][i]&lt;dist[i] ){
                dist[i]=graph[index][i];
                q.push({dist[i],i});
            }
        }
    }
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= n ; ++i) {
        <span class="hljs-keyword">if</span>(!vis[i])<span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>;
    }
    <span class="hljs-keyword">return</span> sum;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> n,m;
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m;
    <span class="hljs-keyword">int</span> inf=<span class="hljs-number">10000000</span>;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dist(n+<span class="hljs-number">1</span>,inf);
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; graph(n+<span class="hljs-number">1</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,inf));
    <span class="hljs-keyword">int</span> a,b,value;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;m;i++){
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;value;
        graph[a][b]=value;
        graph[b][a]=value;
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;prim(graph,dist,n);
}
</code></pre>
<h4 id="2kruskal"><a name="2kruskal" class="anchor-navigation-ex-anchor" href="#2kruskal"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2kruskal" class="plugin-anchor" href="#2kruskal"><i class="fa fa-link" aria-hidden="true"></i></a>2.Kruskal</h4>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">struct</span> Edge{
    <span class="hljs-keyword">int</span> a,b,w;
    Edge(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b ,<span class="hljs-keyword">int</span> w):a(a),b(b),w(w){}
    <span class="hljs-keyword">bool</span> <span class="hljs-keyword">operator</span> &lt; (Edge o)<span class="hljs-keyword">const</span>{
        <span class="hljs-keyword">return</span> w&lt;o.w;
    }
};
<span class="hljs-built_in">vector</span>&lt;Edge&gt; g;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; fa;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x)</span></span>{
    <span class="hljs-keyword">return</span> x==fa[x]?x:fa[x]=find(fa[x]);
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">kruskal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>{
    <span class="hljs-comment">//&#x5BF9;&#x8FB9;&#x8FDB;&#x884C;&#x6392;&#x5E8F;</span>
    sort(g.begin(),g.end());
    <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> cnt=n;
    <span class="hljs-keyword">for</span>(Edge e:g){
        <span class="hljs-keyword">int</span> fax= find(e.a);
        <span class="hljs-keyword">int</span> fay= find(e.b);
        <span class="hljs-keyword">if</span>(fax!=fay){
            <span class="hljs-comment">//&#x8BA1;&#x6570;</span>
            cnt--;
            <span class="hljs-comment">//&#x5408;&#x5E76;</span>
            fa[fax]=fay;
            <span class="hljs-comment">//&#x52A0;&#x4E0A;&#x8FD9;&#x6761;&#x8FB9;&#x7684;&#x503C;</span>
            ans+=e.w;
        }
    }
    <span class="hljs-keyword">return</span> cnt==<span class="hljs-number">1</span>?ans:<span class="hljs-number">-1</span>;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> n,m;
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m;
    <span class="hljs-keyword">int</span> a,b,value;
    fa=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;=n ; ++i) {
        fa[i]=i;
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;m;i++){
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;value;
        g.push_back(Edge(a,b,value));
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;kruskal(n);
}
</code></pre>
<h3 id="3&#x5E76;&#x67E5;&#x96C6;"><a name="3&#x5E76;&#x67E5;&#x96C6;" class="anchor-navigation-ex-anchor" href="#3&#x5E76;&#x67E5;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x5E76;&#x67E5;&#x96C6;" class="plugin-anchor" href="#3&#x5E76;&#x67E5;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x5E76;&#x67E5;&#x96C6;</h3>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> UnionFind{
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">int</span> UnionNums;
    <span class="hljs-keyword">int</span> *graph;
    <span class="hljs-comment">/**
     * find
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{
        <span class="hljs-keyword">if</span>(graph[k]==k)<span class="hljs-keyword">return</span> k;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> k=find(graph[k]);
    }
    <span class="hljs-comment">/**
     * union
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Union</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
        <span class="hljs-keyword">int</span> pI=find(i);
        <span class="hljs-keyword">int</span> pK=find(j);
        <span class="hljs-keyword">if</span>(pI!=pK){
            graph[pK]=pI;
            UnionNums--;
        }
    }

    <span class="hljs-comment">//&#x521D;&#x59CB;&#x5316;</span>
    UnionFind(<span class="hljs-keyword">int</span> nums){
        UnionNums=nums;
        graph=<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[nums+<span class="hljs-number">1</span>];
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;=nums;i++){
            graph[i]=i;
        }
    }
};
</code></pre>
<h3 id="4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><a name="4&#x62D3;&#x6251;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x62D3;&#x6251;&#x6392;&#x5E8F;" class="plugin-anchor" href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x62D3;&#x6251;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">canFinish</span><span class="hljs-params">(<span class="hljs-keyword">int</span> numCourses, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; prerequisites)</span> </span>{
     <span class="hljs-keyword">int</span> len=numCourses;
     <span class="hljs-keyword">int</span> in[len];
     <span class="hljs-keyword">int</span> out[len];
     <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; ve;
     <span class="hljs-built_in">queue</span>&lt;<span class="hljs-keyword">int</span>&gt; q;
     <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v;
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;len;i++){
         in[i]=out[i]=<span class="hljs-number">0</span>;
         ve.push_back(v);
     }

     <span class="hljs-comment">//&#x6784;&#x5EFA;&#x62D3;&#x6251;&#x5E8F;&#x5217;</span>
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;prerequisites.size();i++){
         <span class="hljs-keyword">int</span> l1=prerequisites[i][<span class="hljs-number">0</span>];
         <span class="hljs-keyword">int</span> l2=prerequisites[i][<span class="hljs-number">1</span>];
         ve[l2].push_back(l1);
         in[l1]++;
     }
     <span class="hljs-comment">//&#x5C06;&#x5165;&#x5EA6;&#x4E3A;0&#x7684;&#x653E;&#x5165;&#x961F;&#x5217;</span>
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;len;i++){
         <span class="hljs-keyword">if</span>(in[i]==<span class="hljs-number">0</span>)q.push(i);
     }
     <span class="hljs-keyword">int</span> cnt=<span class="hljs-number">0</span>;
     <span class="hljs-keyword">while</span>(!q.empty()){
         <span class="hljs-keyword">int</span> cur=q.front();
         q.pop();
         cnt++;
         <span class="hljs-comment">//&#x904D;&#x5386;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x7684;&#x90BB;&#x63A5;&#x8868;</span>
         <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;ve[cur].size();i++){
             <span class="hljs-keyword">int</span> c=ve[cur][i];
             in[c]--;
             <span class="hljs-keyword">if</span>(in[c]==<span class="hljs-number">0</span>)q.push(ve[cur][i]);
         }
     }
     <span class="hljs-keyword">return</span> cnt==len;
}
};
</code></pre>
<h2 id="&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;"><a name="&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;" class="anchor-navigation-ex-anchor" href="#&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;" class="plugin-anchor" href="#&#x4E09;-&#x6392;&#x5E8F;&#x6A21;&#x677F;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E09; &#x6392;&#x5E8F;&#x6A21;&#x677F;</h2>
<h3 id="1&#x5FEB;&#x6392;&#x6392;&#x5E8F;"><a name="1&#x5FEB;&#x6392;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#1&#x5FEB;&#x6392;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5FEB;&#x6392;&#x6392;&#x5E8F;" class="plugin-anchor" href="#1&#x5FEB;&#x6392;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5FEB;&#x6392;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">quick_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; &amp; arr, <span class="hljs-keyword">int</span> start ,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-keyword">if</span> ( start&lt;end ){
        <span class="hljs-keyword">int</span> left = start;
        <span class="hljs-keyword">int</span> right = end;
        <span class="hljs-keyword">int</span> pivot= arr[start];
        <span class="hljs-keyword">while</span> (left&lt;right){
            <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;arr[right]&gt;=pivot)right--;
            arr[left]=arr[right];
            <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;arr[left]&lt;=pivot)left++;
            arr[right]=arr[left];
        }
        arr[left]=pivot;
        quick_sort( arr , start,left<span class="hljs-number">-1</span>);
        quick_sort( arr ,left+<span class="hljs-number">1</span>,end);
    }
}
</code></pre>
<h3 id="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><a name="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;" class="plugin-anchor" href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x5F52;&#x5E76;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-comment">//&#x5F52;&#x5E76;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">merge</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr,<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> mid,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; tempArr(end-start+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>);
    <span class="hljs-keyword">int</span> left = start;
    <span class="hljs-keyword">int</span> right = mid+<span class="hljs-number">1</span>;
    <span class="hljs-keyword">int</span> index=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>( left&lt;=mid &amp;&amp; right&lt;=end){
        <span class="hljs-keyword">if</span>( arr[left] &lt;= arr[right] ){
            tempArr[index++]=arr[left++];
        }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(arr[left]&gt;=arr[right]){
            tempArr[index++]=arr[right++];
        }
    }
    <span class="hljs-keyword">while</span>(left&lt;=mid){
        tempArr[index++]=arr[left++];
    }
    <span class="hljs-keyword">while</span>(right&lt;=end){
        tempArr[index++]=arr[right++];
    }
    index=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(start&lt;=end){
        arr[start++]=tempArr[index++];
    }
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">merge_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr,<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-keyword">if</span>(start&lt;end){
        <span class="hljs-keyword">int</span> mid=start+(end-start)/<span class="hljs-number">2</span>;
        merge_sort(arr,start,mid);
        merge_sort(arr,mid+<span class="hljs-number">1</span>,end);
        merge(arr,start,mid, end);
    }
}
</code></pre>
<h3 id="3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><a name="3&#x9009;&#x62E9;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x9009;&#x62E9;&#x6392;&#x5E8F;" class="plugin-anchor" href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x9009;&#x62E9;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">select_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr,<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> end  )</span></span>{
    <span class="hljs-keyword">int</span> swap=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;arr.size()<span class="hljs-number">-1</span> ; ++i) {
        <span class="hljs-keyword">int</span> pos= i;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=i+<span class="hljs-number">1</span>;j&lt;arr.size();j++){
            <span class="hljs-keyword">if</span>( arr[j]&lt;arr[pos] ){
                pos=j;
            }
        }
        swap = arr[pos];
        arr[pos] = arr[i];
        arr[i] = swap;
    }
}
</code></pre>
<h3 id="4&#x5806;&#x6392;&#x5E8F;"><a name="4&#x5806;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#4&#x5806;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x5806;&#x6392;&#x5E8F;" class="plugin-anchor" href="#4&#x5806;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x5806;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> maxdata 100000</span>
<span class="hljs-keyword">struct</span> node{
    <span class="hljs-keyword">int</span> * data;
    <span class="hljs-keyword">int</span> size;
    <span class="hljs-keyword">int</span> capacity;
};
<span class="hljs-keyword">typedef</span> node * tree;
<span class="hljs-function">tree <span class="hljs-title">create</span><span class="hljs-params">(<span class="hljs-keyword">int</span> maxsize)</span></span>{
    tree h=<span class="hljs-keyword">new</span> node;
    h-&gt;data=(<span class="hljs-keyword">int</span> *)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">int</span>)*(maxsize+<span class="hljs-number">1</span>));
    h-&gt;size=<span class="hljs-number">0</span>;
    h-&gt;capacity=maxsize;
    h-&gt;data[<span class="hljs-number">0</span>]=maxdata;
    <span class="hljs-keyword">return</span> h;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">LevelOrderTraversal</span><span class="hljs-params">(tree H)</span></span>{
    <span class="hljs-keyword">int</span> i;
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;&#x5C42;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#xFF1A;&quot;</span>);
    <span class="hljs-keyword">for</span>(i = <span class="hljs-number">1</span>;i&lt;=H-&gt;size;i++){
        <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%d &quot;</span>,H-&gt;data[i]);
    } 
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;\n&quot;</span>); 
} 
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Heapify</span><span class="hljs-params">(tree h,<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">int</span> parent,child;
    <span class="hljs-keyword">int</span> data=h-&gt;data[i];
    <span class="hljs-keyword">for</span>(parent=i;parent*<span class="hljs-number">2</span>&lt;=h-&gt;size;parent=child){
        child=parent*<span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span>(child!=h-&gt;size){
            <span class="hljs-keyword">if</span>(h-&gt;data[child]&lt;h-&gt;data[child+<span class="hljs-number">1</span>])child++;
        }
        <span class="hljs-keyword">if</span>(h-&gt;data[child]&lt;=data)<span class="hljs-keyword">break</span>;
        <span class="hljs-keyword">else</span> h-&gt;data[parent]=h-&gt;data[child];
    }
    h-&gt;data[parent]=data;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">adjust</span><span class="hljs-params">(tree h)</span></span>{
    <span class="hljs-keyword">int</span> i=h-&gt;size/<span class="hljs-number">2</span>;
    <span class="hljs-keyword">for</span>(;i&gt;<span class="hljs-number">0</span>;i--){
        Heapify(h,i);<span class="hljs-comment">//&#x4ECE;&#x6700;&#x62E5;&#x6709;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x6811;&#x5F00;&#x59CB;--&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x7279;&#x6027;,&#x53EF;&#x4EE5;&#x81EA;&#x5DF1;&#x753B;&#x4E2A;&#x56FE;&#x9A8C;&#x8BC1;&#x4E00;&#x4E0B;</span>
    } 
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    tree h;
    h=create(<span class="hljs-number">100</span>);
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span>&gt;&gt;n;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-built_in">cin</span>&gt;&gt;h-&gt;data[++h-&gt;size];
    }
    adjust(h);
    LevelOrderTraversal(h);
}
</code></pre>
<h3 id="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><a name="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;" class="plugin-anchor" href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>5.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-comment">//4.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">shell_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr , <span class="hljs-keyword">int</span> n)</span></span>{
    <span class="hljs-keyword">for</span>( <span class="hljs-keyword">int</span> gap=n/<span class="hljs-number">2</span>; gap&gt;<span class="hljs-number">0</span> ;gap/=<span class="hljs-number">2</span>){
        <span class="hljs-keyword">for</span>( <span class="hljs-keyword">int</span> i=gap ;i&lt;arr.size();i+=gap){
            <span class="hljs-keyword">int</span> j=i;
            <span class="hljs-keyword">int</span> sentinel= arr[i];
            <span class="hljs-keyword">if</span>( arr[j]&lt;arr[j-gap] ){
                <span class="hljs-keyword">while</span>( j-gap&gt;=<span class="hljs-number">0</span> &amp;&amp; arr[j-gap] &gt; sentinel ){
                    arr[j]= arr[j-gap];
                    j-=gap;
                }
                arr[j]= sentinel;
            }
        }
    }
}
</code></pre>
<h3 id="6&#x57FA;&#x6570;&#x6392;&#x5E8F;"><a name="6&#x57FA;&#x6570;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#6&#x57FA;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="6&#x57FA;&#x6570;&#x6392;&#x5E8F;" class="plugin-anchor" href="#6&#x57FA;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>6.&#x57FA;&#x6570;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-c++"><span class="hljs-comment">/*
 * &#x83B7;&#x53D6;&#x6570;&#x7EC4;a&#x4E2D;&#x6700;&#x5927;&#x503C;
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 */</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">get_max</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n)</span>
</span>{
    <span class="hljs-keyword">int</span> i, max;

    max = a[<span class="hljs-number">0</span>];
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>; i &lt; n; i++)
        <span class="hljs-keyword">if</span> (a[i] &gt; max)
            max = a[i];
    <span class="hljs-keyword">return</span> max;
}

<span class="hljs-comment">/*
 * &#x5BF9;&#x6570;&#x7EC4;&#x6309;&#x7167;&quot;&#x67D0;&#x4E2A;&#x4F4D;&#x6570;&quot;&#x8FDB;&#x884C;&#x6392;&#x5E8F;(&#x6876;&#x6392;&#x5E8F;)
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 *     exp -- &#x6307;&#x6570;&#x3002;&#x5BF9;&#x6570;&#x7EC4;a&#x6309;&#x7167;&#x8BE5;&#x6307;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
 *
 * &#x4F8B;&#x5982;&#xFF0C;&#x5BF9;&#x4E8E;&#x6570;&#x7EC4;a={50, 3, 542, 745, 2014, 154, 63, 616}&#xFF1B;
 *    (01) &#x5F53;exp=1&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x4E2A;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    (02) &#x5F53;exp=10&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x5341;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    (03) &#x5F53;exp=100&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x767E;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    ...
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">count_sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> <span class="hljs-built_in">exp</span>)</span>
</span>{
    <span class="hljs-keyword">int</span> output[n];             <span class="hljs-comment">// &#x5B58;&#x50A8;&quot;&#x88AB;&#x6392;&#x5E8F;&#x6570;&#x636E;&quot;&#x7684;&#x4E34;&#x65F6;&#x6570;&#x7EC4;</span>
    <span class="hljs-keyword">int</span> i, buckets[<span class="hljs-number">10</span>] = {<span class="hljs-number">0</span>};

    <span class="hljs-comment">// &#x5C06;&#x6570;&#x636E;&#x51FA;&#x73B0;&#x7684;&#x6B21;&#x6570;&#x5B58;&#x50A8;&#x5728;buckets[]&#x4E2D;</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n; i++)
        buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ]++;

    <span class="hljs-comment">// &#x66F4;&#x6539;buckets[i]&#x3002;&#x76EE;&#x7684;&#x662F;&#x8BA9;&#x66F4;&#x6539;&#x540E;&#x7684;buckets[i]&#x7684;&#x503C;&#xFF0C;&#x662F;&#x8BE5;&#x6570;&#x636E;&#x5728;output[]&#x4E2D;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>; i &lt; <span class="hljs-number">10</span>; i++)
        buckets[i] += buckets[i - <span class="hljs-number">1</span>];

    <span class="hljs-comment">// &#x5C06;&#x6570;&#x636E;&#x5B58;&#x50A8;&#x5230;&#x4E34;&#x65F6;&#x6570;&#x7EC4;output[]&#x4E2D;</span>
    <span class="hljs-keyword">for</span> (i = n - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; i--)
    {
        output[buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ] - <span class="hljs-number">1</span>] = a[i];
        buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ]--;
    }

    <span class="hljs-comment">// &#x5C06;&#x6392;&#x5E8F;&#x597D;&#x7684;&#x6570;&#x636E;&#x8D4B;&#x503C;&#x7ED9;a[]</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n; i++)
        a[i] = output[i];
}

<span class="hljs-comment">/*
 * &#x57FA;&#x6570;&#x6392;&#x5E8F;
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">radix_sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n)</span>
</span>{
    <span class="hljs-keyword">int</span> <span class="hljs-built_in">exp</span>;    <span class="hljs-comment">// &#x6307;&#x6570;&#x3002;&#x5F53;&#x5BF9;&#x6570;&#x7EC4;&#x6309;&#x5404;&#x4F4D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x65F6;&#xFF0C;exp=1&#xFF1B;&#x6309;&#x5341;&#x4F4D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x65F6;&#xFF0C;exp=10&#xFF1B;...</span>
    <span class="hljs-keyword">int</span> max = get_max(a, n);    <span class="hljs-comment">// &#x6570;&#x7EC4;a&#x4E2D;&#x7684;&#x6700;&#x5927;&#x503C;</span>

    <span class="hljs-comment">// &#x4ECE;&#x4E2A;&#x4F4D;&#x5F00;&#x59CB;&#xFF0C;&#x5BF9;&#x6570;&#x7EC4;a&#x6309;&quot;&#x6307;&#x6570;&quot;&#x8FDB;&#x884C;&#x6392;&#x5E8F;</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-built_in">exp</span> = <span class="hljs-number">1</span>; max/<span class="hljs-built_in">exp</span> &gt; <span class="hljs-number">0</span>; <span class="hljs-built_in">exp</span> *= <span class="hljs-number">10</span>)
        count_sort(a, n, <span class="hljs-built_in">exp</span>);
}
</code></pre>
<h3 id="7&#x6876;&#x6392;&#x5E8F;"><a name="7&#x6876;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#7&#x6876;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="7&#x6876;&#x6392;&#x5E8F;" class="plugin-anchor" href="#7&#x6876;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>7.&#x6876;&#x6392;&#x5E8F;</h3>
<pre><code class="lang-java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">bucketSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span></span>{

    <span class="hljs-comment">// &#x8BA1;&#x7B97;&#x6700;&#x5927;&#x503C;&#x4E0E;&#x6700;&#x5C0F;&#x503C;</span>
    <span class="hljs-keyword">int</span> max = Integer.MIN_VALUE;
    <span class="hljs-keyword">int</span> min = Integer.MAX_VALUE;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    <span class="hljs-comment">// &#x8BA1;&#x7B97;&#x6876;&#x7684;&#x6570;&#x91CF;</span>
    <span class="hljs-keyword">int</span> bucketNum = (max - min) / arr.length + <span class="hljs-number">1</span>;
    ArrayList&lt;ArrayList&lt;Integer&gt;&gt; bucketArr = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;(bucketNum);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketNum; i++){
        bucketArr.add(<span class="hljs-keyword">new</span> ArrayList&lt;Integer&gt;());
    }

    <span class="hljs-comment">// &#x5C06;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x653E;&#x5165;&#x6876;</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++){
        <span class="hljs-keyword">int</span> num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }

    <span class="hljs-comment">// &#x5BF9;&#x6BCF;&#x4E2A;&#x6876;&#x8FDB;&#x884C;&#x6392;&#x5E8F;</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }

    <span class="hljs-comment">// &#x5C06;&#x6876;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x8D4B;&#x503C;&#x5230;&#x539F;&#x5E8F;&#x5217;</span>
    <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketArr.size(); i++){
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; bucketArr.get(i).size(); j++){
            arr[index++] = bucketArr.get(i).get(j);
        }
    }  
}
</code></pre>
<h2 id="&#x56DB;-&#x6563;&#x5217;&#x8868;"><a name="&#x56DB;-&#x6563;&#x5217;&#x8868;" class="anchor-navigation-ex-anchor" href="#&#x56DB;-&#x6563;&#x5217;&#x8868;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x56DB;-&#x6563;&#x5217;&#x8868;" class="plugin-anchor" href="#&#x56DB;-&#x6563;&#x5217;&#x8868;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x56DB; &#x6563;&#x5217;&#x8868;</h2>
<h3 id="1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;"><a name="1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;" class="anchor-navigation-ex-anchor" href="#1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;" class="plugin-anchor" href="#1&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x6CD5;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> MAXTABLESIZE 100000   <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x5141;&#x8BB8;&#x5F00;&#x8F9F;&#x7684;&#x6700;&#x5927;&#x6563;&#x5217;&#x8868;&#x957F;&#x5EA6; </span></span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">int</span> Index;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">int</span> ElementType; 
<span class="hljs-keyword">typedef</span> Index Position;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">enum</span>{   <span class="hljs-comment">// &#x5206;&#x522B;&#x5BF9;&#x5E94;&#xFF1A;&#x6709;&#x5408;&#x6CD5;&#x5143;&#x7D20;&#x3001;&#x7A7A;&#x3001;&#x6709;&#x5DF2;&#x5220;&#x9664;&#x5143;&#x7D20; </span>
    Legitimate,Empty,Deleted
} EntryType;  <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x5355;&#x5143;&#x72B6;&#x6001;&#x7C7B;&#x578B; </span>

<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> HashEntry Cell;
<span class="hljs-keyword">struct</span> HashEntry{   <span class="hljs-comment">//  &#x54C8;&#x5E0C;&#x8868;&#x5B58;&#x503C;&#x5355;&#x5143; </span>
    ElementType Data;  <span class="hljs-comment">// &#x5B58;&#x653E;&#x5143;&#x7D20;</span>
    EntryType Info;  <span class="hljs-comment">// &#x5355;&#x5143;&#x72B6;&#x6001;    </span>
};

<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> HashTbl *HashTable;
<span class="hljs-keyword">struct</span> HashTbl{  <span class="hljs-comment">// &#x54C8;&#x5E0C;&#x8868;&#x7ED3;&#x6784;&#x4F53; </span>
    <span class="hljs-keyword">int</span> TableSize;   <span class="hljs-comment">// &#x54C8;&#x5E0C;&#x8868;&#x5927;&#x5C0F; </span>
    Cell *Cells;   <span class="hljs-comment">// &#x54C8;&#x5E0C;&#x8868;&#x5B58;&#x503C;&#x5355;&#x5143;&#x6570;&#x7EC4; </span>
};

<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">NextPrime</span><span class="hljs-params">(<span class="hljs-keyword">int</span> N)</span></span>;  <span class="hljs-comment">// &#x67E5;&#x627E;&#x7D20;&#x6570; </span>
<span class="hljs-function">HashTable <span class="hljs-title">CreateTable</span><span class="hljs-params">( <span class="hljs-keyword">int</span> TableSize)</span></span>; <span class="hljs-comment">// &#x521B;&#x5EFA;&#x54C8;&#x5E0C;&#x8868; </span>
<span class="hljs-function">Index <span class="hljs-title">Hash</span><span class="hljs-params">(<span class="hljs-keyword">int</span> Key,<span class="hljs-keyword">int</span> TableSize)</span></span>;   <span class="hljs-comment">// &#x54C8;&#x5E0C;&#x51FD;&#x6570; </span>

<span class="hljs-comment">// &#x67E5;&#x627E;&#x7D20;&#x6570; </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">NextPrime</span><span class="hljs-params">(<span class="hljs-keyword">int</span> N)</span></span>{
    <span class="hljs-keyword">int</span> p = (N%<span class="hljs-number">2</span>)?N+<span class="hljs-number">2</span>:N+<span class="hljs-number">1</span>;  <span class="hljs-comment">// &#x4ECE;&#x5927;&#x4E8E; N &#x7684;&#x4E0B;&#x4E2A;&#x5947;&#x6570;&#x5F00;&#x59CB;</span>
    <span class="hljs-keyword">int</span> i;

    <span class="hljs-keyword">while</span>(p &lt;= MAXTABLESIZE){
        <span class="hljs-keyword">for</span>(i = (<span class="hljs-keyword">int</span>)<span class="hljs-built_in">sqrt</span>(p);i&gt;<span class="hljs-number">2</span>;i--)
            <span class="hljs-keyword">if</span>(!(p%i))  <span class="hljs-comment">// p &#x4E0D;&#x662F;&#x7D20;&#x6570; </span>
                <span class="hljs-keyword">break</span>;
        <span class="hljs-keyword">if</span>(i==<span class="hljs-number">2</span>) 
            <span class="hljs-keyword">break</span>; 
        p += <span class="hljs-number">2</span>;  <span class="hljs-comment">// &#x7EE7;&#x7EED;&#x8BD5;&#x63A2;&#x4E0B;&#x4E2A;&#x5947;&#x6570; </span>
    }
    <span class="hljs-keyword">return</span> p;
}

<span class="hljs-comment">// &#x521B;&#x5EFA;&#x54C8;&#x5E0C;&#x8868; </span>
<span class="hljs-function">HashTable <span class="hljs-title">CreateTable</span><span class="hljs-params">( <span class="hljs-keyword">int</span> TableSize)</span></span>{
    HashTable H;
    <span class="hljs-keyword">int</span> i;
    H = (HashTable)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> HashTbl));
    <span class="hljs-comment">// &#x4FDD;&#x8BC1;&#x54C8;&#x5E0C;&#x8868;&#x6700;&#x5927;&#x957F;&#x5EA6;&#x662F;&#x7D20;&#x6570; </span>
    H-&gt;TableSize = NextPrime(TableSize);
    <span class="hljs-comment">// &#x521D;&#x59CB;&#x5316;&#x5355;&#x5143;&#x6570;&#x7EC4;</span>
    H-&gt;Cells = (Cell *)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(Cell)*H-&gt;TableSize);
    <span class="hljs-comment">// &#x521D;&#x59CB;&#x5316;&#x5355;&#x5143;&#x6570;&#x7EC4;&#x72B6;&#x6001; </span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;H-&gt;TableSize;i++)
        H-&gt;Cells[i].Info = Empty;
    <span class="hljs-keyword">return</span> H;
}

<span class="hljs-comment">// &#x5E73;&#x65B9;&#x63A2;&#x6D4B;&#x67E5;&#x627E; </span>
<span class="hljs-function">Position <span class="hljs-title">Find</span><span class="hljs-params">(HashTable H,ElementType Key)</span></span>{
    Position CurrentPos,NewPos; 
    <span class="hljs-keyword">int</span> CNum = <span class="hljs-number">0</span> ;   <span class="hljs-comment">// &#x8BB0;&#x5F55;&#x51B2;&#x7A81;&#x6B21;&#x6570;</span>
    CurrentPos = NewPos = Hash(Key,H-&gt;TableSize);
    <span class="hljs-comment">// &#x5982;&#x679C;&#x5F53;&#x524D;&#x5355;&#x5143;&#x72B6;&#x6001;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C;&#x4E14;&#x6570;&#x503C;&#x4E0D;&#x7B49;&#xFF0C;&#x5219;&#x4E00;&#x76F4;&#x505A; </span>
    <span class="hljs-keyword">while</span>(H-&gt;Cells[NewPos].Info != Empty &amp;&amp; H-&gt;Cells[NewPos].Data != Key){
        <span class="hljs-keyword">if</span>(++CNum % <span class="hljs-number">2</span> ){ <span class="hljs-comment">// &#x51B2;&#x7A81;&#x5947;&#x6570;&#x6B21;&#x53D1;&#x751F; </span>
            NewPos = CurrentPos + (CNum+<span class="hljs-number">1</span>)/<span class="hljs-number">2</span>*(CNum+<span class="hljs-number">1</span>)/<span class="hljs-number">2</span>;
            <span class="hljs-comment">// &#x5982;&#x679C;&#x8D8A;&#x754C;&#xFF0C;&#x4E00;&#x76F4;&#x51CF;&#x76F4;&#x5230;&#x518D;&#x6B21;&#x8FDB;&#x5165;&#x8FB9;&#x754C; </span>
            <span class="hljs-keyword">while</span>(H-&gt;TableSize &lt;= NewPos){
                NewPos -= H-&gt;TableSize; 
            }
        }<span class="hljs-keyword">else</span>{  <span class="hljs-comment">// &#x51B2;&#x7A81;&#x5076;&#x6570;&#x6B21;&#x53D1;&#x751F; </span>
            NewPos = CurrentPos - CNum/<span class="hljs-number">2</span>*CNum/<span class="hljs-number">2</span>;
            <span class="hljs-comment">// &#x5982;&#x679C;&#x8D8A;&#x754C;&#xFF0C;&#x4E00;&#x76F4;&#x52A0;&#x76F4;&#x5230;&#x518D;&#x6B21;&#x8FDB;&#x5165;&#x8FB9;&#x754C; </span>
            <span class="hljs-keyword">while</span>(NewPos &lt; <span class="hljs-number">0</span>){
                NewPos += H-&gt;TableSize; 
            }
        }
    } 
    <span class="hljs-keyword">return</span> NewPos;
}

<span class="hljs-comment">// &#x63D2;&#x5165;</span>
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">Insert</span><span class="hljs-params">( HashTable H,ElementType Key,<span class="hljs-keyword">int</span> i)</span></span>{
    Position Pos = i;
    Pos = Find(H,Key);
    <span class="hljs-comment">// &#x5982;&#x679C;&#x5355;&#x5143;&#x683C;&#x72B6;&#x6001;&#x4E0D;&#x662F;&quot;&#x5B58;&#x5728;&#x5408;&#x6CD5;&#x5143;&#x7D20;&quot; </span>
    <span class="hljs-keyword">if</span>( H-&gt;Cells[Pos].Info != Legitimate){
        H-&gt;Cells[Pos].Info = Legitimate;
        H-&gt;Cells[Pos].Data = Key;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
} 

<span class="hljs-comment">// &#x9664;&#x7559;&#x4F59;&#x6570;&#x6CD5;&#x54C8;&#x5E0C;&#x51FD;&#x6570; </span>
<span class="hljs-function">Index <span class="hljs-title">Hash</span><span class="hljs-params">(<span class="hljs-keyword">int</span> Key,<span class="hljs-keyword">int</span> TableSize)</span></span>{
    <span class="hljs-keyword">return</span> Key % TableSize;
}
</code></pre>

<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="7.树论例题.html" class="navigation navigation-prev " aria-label="Previous page: 7.树论例题.md">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="../算法/leetCode周赛题解.html" class="navigation navigation-next " aria-label="Next page: leetCode周赛记录">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"数据结构模板","level":"3.8","depth":1,"next":{"title":"leetCode周赛记录","level":"4.1","depth":1,"path":"算法/leetCode周赛题解.md","ref":"算法/leetCode周赛题解.md","articles":[]},"previous":{"title":"7.树论例题.md","level":"3.7","depth":1,"path":"数据结构/7.树论例题.md","ref":"数据结构/7.树论例题.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"数据结构/9.模板.md","mtime":"2020-12-30T07:51:07.477Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

